char* blank(int n) {
    char* str = (char*)malloc((n + 1) * sizeof(char));  // 动态分配内存
    for (int i = 0; i < n; i++) {
        str[i] = ' ';  // 逐个填充空格字符
    }
    str[n] = '\0';  // 字符串末尾加上 NUL 字符
    return str;
}

char* join(char* words[], int left, int right, char* sep) {
    if (left >= right) {
        return NULL;  // 如果起点大于等于终点，返回 NULL，表示出错
    }
    int total_length = strlen(words[left]);  // 总字符数初始化为 words[left] 长度
    for (int i = left + 1; i < right; i++) {
        total_length += strlen(sep) + strlen(words[i]);  // 加上分隔符和每个字符串长度
    }

    char* res = (char*)malloc((total_length + 1) * sizeof(char));  // 动态分配内存
    strcpy(res, words[left]);  // 复制 words[left] 到结果字符串中
    for (int i = left + 1; i < right; i++) {
        strcat(res, sep);  // 拼接分隔符
        strcat(res, words[i]);  // 拼接字符串
    }
    return res;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char** fullJustify(char** words, int wordsSize, int maxWidth, int* returnSize) {
    char** ans = (char**)malloc(10000 * sizeof(char*));
    int left = 0, right = 0;
    int index = 0;
    while (1) { // 这里的 1 代表 true
        // 1. 确定当前行可以放哪些单词
        left = right;
        int sumLen = 0;
        while (right < wordsSize && sumLen + strlen(words[right]) + (right - left) <= maxWidth) {
            sumLen += strlen(words[right]);
            right++;
        }

        if (right == wordsSize) {
            // 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
            ans[index] = (char*)malloc((maxWidth + 1) * sizeof(char));
            char* temp = join(words, left, right, " ");
            strcpy(ans[index], temp);
            strcat(ans[index], blank(maxWidth - strlen(temp)));
            *returnSize = index + 1;
            return ans;
        }

        int numWords = right - left;
        int numSpaces = maxWidth - sumLen;
        if (numWords == 1) {
            // 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
            ans[index] = (char*)malloc((maxWidth + 1) * sizeof(char));
            strcpy(ans[index], words[left]);
            strcat(ans[index], blank(numSpaces));
            *returnSize = index + 1;
            index++;
            continue;
        }

        // 当前行不只一个单词
        // 计算两个单词之间需要多少个空格 （求平均值，因为要均匀分配）
        int avgSpaces = numSpaces / (numWords - 1);
        int extraSpaces = numSpaces % (numWords - 1);
        ans[index] = (char*)malloc((maxWidth + 1) * sizeof(char));
        strcpy(ans[index], join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1)));
        strcat(ans[index], blank(avgSpaces));
        strcat(ans[index], join(words, left + extraSpaces + 1, right, blank(avgSpaces)));

        *returnSize = index + 1;
        index++;
    }
}